Business Shareware/Business Shareware.iso/start/gfxapps/grphme10/technicl.doc

Text File | 1992-11-15 | 8KB | 147 lines

     Well, if you want to get into the nitty-gritty of how
     Graph-Me! works, read on.  If not, skip over this and into
     the next article.  Be sure to read GRAPHME.DOC.


THE BASICS:
     The technology behind Graph-Me!'s equation interpreter is
     called Recursive Descent Parsing.  What that means is that a
     small ammount of code is used over and over again
     (recursive), at seperate levels (descent), until the
     equation is parsed (taken from human language and put into
     machine language).  I do this by breaking the entire line
     into 'tokens', and then dividing these tokens into four
     major groups, which I quite generically call 'level0'
     through 'level3'.  The schematic of this break-up follows.

     level0:
          level1 {+, -} level1 ... EOL,')'
     level1:
          level2 {*,/,%,^} level2 ...
     level2:
          {{sin, cos, ln, exp ...} level2 , level3}
     level3:
          {{-}<Number>, '('level0')'}

     (In understanding this schematic, items in curly brackets
     ('{','}') and seperated by ',' denote options, one or the
     other.  'level1' denotes any level1 expression should be
     inserted at that place, etc.)

     As you can see, the 'recursive' part of the algorithm comes
     from going all the way through the heirarchy and
     encounterring an open parentheses, which forces us back to
     the top of the hierarchy (level0).

     Using this structure as a basis, it is easy to see that the
     basic rules of arithmetic are observed -- the hierarchy and
     the parentheses override, everything else left-to-right.

     Some small factors, however, are worth noting because they
     are not specified in the arithmetic rules.  For instance,
     the modulus and power operators (%,^) are of the same level
     as the multiplication and divide (*,/).  This means that a
     line of the sort '3*2^4*5' is read as '((3*2)^4)*5', because
     it is simply translated left-to-right.  Some people find
     this intuitive while others find it counter-intuitive.  I
     would like feedback on this so that later versions are as
     close to a 'standard' as possible.  (Some people see the
     line as '3*(2^4)*5', rather than what it actually comes out
     to be.)  This area is further blurred by the lt and gt
     (greatest integer less than and least integer greater than)
     operators, which are so seldom used that they have *no*
     intuitiveness at all -- at least not to me.
     All of this is done before any graphing starts.  The result
     of this tokenization is a compact, yet unique, array of
     tokens which define the equation you put in.

PLOTTING:
     Once we have done a pre-calculation on the input line (it is
     in an array of tokens rather than a cryptic string), all
     that is left to do is put a bit of form to it.  Graph-Me!
     works by setting the first independent variable as a
     constant, and then varying the second independent variable
     from its minimum value to its maximum value.  Straight lines
     are drawn between each data point to eliminate horizontal
     gaps and in order to allow less-than-screen-accuracy images
     to look smooth.  Before each line is drawn, it is transfered
     from 3-d space to screen-space.

     Currently, each line is independant of each other line; no
     value is used twice.  This can be rather inefficient,
     especially at low accuracy settings (high numbers, > 10).
     In the near future I hope to add a 'Matrix' option which
     will allow a faster on-screen representation by reducing the
     number of calculations taken to the number of vertices which
     exist on the graph, within the bounds.  In other words,
     whereas now everything is nice and smooth between vertices,
     the 'Matrix' option will reduce the accuracy until graph
     consists of straight lines, from vertice to vertice.  Also,
     the 'Matrix' option will eliminate 'double-calculating' of
     data points by keeping points in memory longer.  This should
     increase the speed tenfold at the least, giving a very rough
     sketch of the layout of the graph and almost-realtime
     rotation.  I also hope to develope a proprietary method for
     saving images in this form so that total recalculation is
     not necessary.

     Back to the present, Graph-Me! writes this information to
     screen, then forgets it.  This is good, considerring a very
     low resolution image contains 1.2 Mb of information
     (640x480x4 bytes per data point), and a higher res. image,
     or one in which the x-y plane is not parallel to the screen,
     quickly would eat up the memory.  I have briefly considerred
     being able to do a total save of this (so that a full-
     quality image could be brought up within minutes), but
     decided against it, since few of us have ten Megs or so of
     free disk space.  If there is an interrest, I'll work on it,
     but I foresee no demand at present.

     But, since Graph-Me! simply forgets all it has worked so
     hard to calculate, the slightest twist, turn, or zoom
     requires a full redraw of the image.  Beware this!  There is
     nothing worse than waiting fifteen minutes for an image to
     be drawn, only to find that it needs just a smidgen more
     rotation this way or that ...
TIPS:
     Well, I suppose the last sentence in the preceeding section
     is the first tip I can give you.  If getting a nice print-
     out of just the right angle of a graph is important to you,
     *Preview the Graph First* by setting the accuracy to ten or
     so, then put it back down to two or three for the final
     product.

     Secondly, an accuracy of one is often quite wasteful.  The
     'one' refers to, if the x-y plane were put parallel to the
     screen, one pixel straight down from the center of the
     screen.  It doesn't take a lot of rotation before an
     accuracy rating of 'two' gives you pixel-accuracy, and just
     a bit more before a rating of *three* gives you pixel
     accuracy.  Look at it for yourself.  If the lines seem to
     wiggle back and forth a lot (this is due to round-off error
     in your computer's CPU), increase the accuracy rating a bit.
     (Remember, a higher accuracy rating means a less accurate
     depiction).  If your 'sin' wave looks like a bunch of
     straight lines, decrease the rating a few pixels until it
     looks right.  You have to eye it for now, until I get the
     code in place to put it at pixel accuracy automatically.

     Third, if a formula seems to generate a strange graph, put
     the equation through the calculator (substituting actual
     values for the variables, of course) and see if my
     calculations routine is doing what you expect.  Two notable
     possibilities for error are listed above, in the general
     description of the parser.

     Finally, a faster computer makes all the difference in the
     world.  This program is extremely calculation dependant, and
     therefore would benifit *greatly* from a faster cpu.  I
     currently do not have support for the fpu (80x87), but that
     should be coming within the first few versions.  If you find
     that a simple graph takes hours to graph, move on up past
     the 286 line and into something meatier, ('486 highly
     recommended) or, if your funds are not quite equal to those
     of Ross Perot, sneak this program onto a friend's fast
     computer and graph away!